#include <iostream>
#include <vector>

using namespace std;


bool VerifySquenceOfBST(vector<int> sequence) {
	int i = 0, ssize = sequence.size();
	if (ssize == 0) return false;
	int root = sequence[ssize - 1];
	vector<int> left, right;
	bool leftJudge = false, rightJudge = false;
	while (sequence[i] < root && i < ssize - 1)
	{
		left.push_back(sequence[i]);
		++i;
	}
	for (; i < ssize - 1; ++i)
	{
		if (sequence[i] > root)
			right.push_back(sequence[i]);
		else
			return false;
	}
	if (left.size() != 0)
		leftJudge = VerifySquenceOfBST(left);
	else 
		leftJudge = true;
	if (right.size() != 0)
		rightJudge = VerifySquenceOfBST(right);
	else
		rightJudge = true;
	return leftJudge&&rightJudge;
}

bool VerifySquenceOfBST2(vector<int> sequence) {
	if (sequence.size() == 0)
		return false;
	if (sequence.size() == 1)
		return true;

	vector<int>::const_iterator root = sequence.end() - 1;
	int rootVal = *root;

	vector<int>::const_iterator split;
	vector<int> left, right;
	for (split = sequence.begin(); split != root; ++split)
	{
		if (*split < rootVal)
			left.push_back(*split);
		else if (*split == rootVal)
			return false;
		else
			break;
	}
	for (; split != root; ++split)
	{
		if (*split > rootVal)
			right.push_back(*split);
		else if (*split <= rootVal)
			return false;

	}
	bool leftJudge(true), rightJudge(true);
	if (left.size() != 0)
		leftJudge = VerifySquenceOfBST(left);
	if (right.size() != 0)
		rightJudge = VerifySquenceOfBST(right);

	return rightJudge&&leftJudge;
}

//int main()
//{
//	vector<int> v = { 1,3,2,4,6,8,7,5 };
//	cout << VerifySquenceOfBST(v) << endl;
//
//
//	system("pause");
//	return 0;
//}